
        <html>
			<head>
			     <title>反编译系列教程(上) - MalwareBenchmark</title>
				 <meta http-equiv="content-type" content="text/html; charset=UTF-8">
			</head>
			<body>
				<h1>原文地址:<a href="http://drops.wooyun.org/papers/13686">http://drops.wooyun.org/papers/13686</a></h1>
				
      <p>
        <p><strong>Author: MalwareBenchmark</strong></p>

<h1>0x00 简介</h1>

<p>《编译原理》课程在大学本科阶段就难道了很多计算机专业的同学。而反编译技术更需要从事者具有深厚的编译技术基础，因此一直是很多业内人士希望能够深入了解和掌握的一门技术。</p>

<p>从现在开始，我们讨论反向编译的一些内容。顾名思义，反编译可以认为是编译的逆过程，这一点从编译和反编译（Compile and De-compile，英文中也有用De-compilation来表示反编译的）的中英文描述都可看出。但这看似只有一字之差的名称，在实际应用中并不是简单的“逆流而上”。因为在多数时候“创造”远比“恢复”来得简单，就好像您不小心打碎了家里的花瓶，想要通过修复和粘接把碎片恢复成原样，几乎是不可能办到的。即便能够基本复原，但粘接的花瓶与它原来的样子也不会完全一样。与碎片到花瓶的变化类似，反编译过程远比编译过程复杂和繁琐，而且反编译的结果也远远不如您原来编写的代码那么“美妙”。但是反向编译却能在程序功能分析、恶意代码发现、二进制翻译等特殊工作中发挥重要作用，这也是笔者仍然致力于研究这一并不十分完善的技术的重要原因。</p>

<!--more-->

<h1>0x01 反编译的概念和基本过程</h1>

<hr />

<h3>1.什么是反编译</h3>

<p>在这一节里我们将对反编译做出一个基本的说明，给出反编译的概念，使读者们可以对反编译有一个初步的理解。我们给出的概念不是学术研究中严谨的定义，只是作者基于相关文献和多年来的研究心得所给出的一段说明。此外，我们还会揭示一个事实，尽管编译与反编译看起来是正反两项技术，但有趣的是：反编译器的编写方法却恰恰依赖于编译器的编写技术。</p>

<p><strong>反编译概念</strong></p>

<p>反编译技术是通过对低级语言代码（二进制代码或者汇编代码等）进行分析转化，得到等价的高级语言（不限制语言类型，本书的描述主要以C语言为例）代码的过程。它涉及指令系统，可执行文件格式，反汇编技术，数据类型分析技术，控制流分析技术和高级代码生成技术等。</p>

<p><strong>编译与反编译</strong></p>

<p>反编译的本质是编译的逆过程。从二十世纪五十年代第一个编译器出现开始，将机器码转换成为高级语言的期望就引发了人们广泛的兴趣。图1揭示了编译器同反编译器之间的关系。</p>

<p>可以看到编译器同反编译器都将程序从一种形式转换到另外一种形式，而且在转换的步骤中，都使用了类似的中间表示。差别只是在于编译器的总体方向是从源程序到机器码，而反编译器的总体方向则是从机器码到源程序。尽管在整体方向上两者是相反的，但编译器和反编译器往往在分析阶段使用类似的技术，例如数据流分析。</p>

<p>编译器通过对源代码进行解析得到中间表示（IR，intermediaterepresentation），反编译器通过对指令进行解码得到中间表示。类似的，编译器的低级代码生成同反编译器的高级代码生成恰好对应。</p>

<p><img src="http://static.wooyun.org//drops/20160307/20160307125921163851-1.jpg" alt="1-1" /></p>

<p>图1 编译器同反编译器在结构上的对应性</p>

<p>编译的过程为源程序打上了机器属性，比如CPU及寄存器的使用、机器指令的使用、以及内存地址的分配等；而反编译过程则需要剥离机器相关的细节，尽可能地区分指令和数据，通过逆向分析，重建高级数据结构和程序结构。</p>

<p><strong>反编译器</strong></p>

<p>反编译器是利用反编译技术实现的具体软件系统。它读入一个机器语言的程序（被编译器编译生成的二进制编码，即源语言），并把它翻译为一个等价的高级语言程序（即目标语言）。反编译器或反向编译器，尝试逆向一个编译器的过程，把一个二进制程序或可执行程序翻译成一个高级语言程序。它应用基本的反编译器技术，把多种多样的机器语言二进制程序反编译成某种高级语言。反编译器的结构是基于编译器的结构，而且应用类似的原理和技术进行程序分析。</p>

<h3>2.反编译的基本过程</h3>

<p>在这一小节，我们按照三种不同的分类，从多个角度阐述反编译的基本过程。</p>

<ol>
<li><p>如果按照反编译技术实施的顺序划分，则可以分为7个阶段，它们是：句法分析、语义分析、中间代码生成、控制流图生成、控制流分析、代码生成。如图所示。</p>

<p><img src="http://static.wooyun.org//drops/20160307/20160307125922493061-2.jpg" alt="1-2" /></p>

<p>图2 按照反编译技术实施的顺序划分</p></li>
<li><p>如果按照实践中的具体操作划分，一般也可以分为7个不同的步骤，分别是：文件装载，指令解码，语义映射，相关图构造，过程分析，类型分析和结果输出等。如图 3。</p>

<p><img src="http://static.wooyun.org//drops/20160307/20160307125923965021-3.jpg" alt="1-3" /></p>

<p>图3 反编译操作</p>

<p>以逆向分析为目的，反编译的各个阶段并不是一个严格的一遍顺序，而是存在着一些并行的模块，并且也需要通过循环执行分析过程来针对某些特殊问题（例如非N分支代码产生的间接跳转指令）进行分析和恢复。</p></li>
<li><p>反编译的处理过程，如果按功能区分，可以分为：前端、中端和后端三个部分。其实这种划分方式是将上述两种过程的阶段进行合并，也就是将几个反编译器阶段组合在一起。这样划分的好处是：通过设计不同的前端、中端和后端以实现针对多种源和目标的反编译器。</p></li>
</ol>

<h1>0x02 反编译的前世今生</h1>

<hr />

<h3>1.建立——20世纪60年代</h3>

<p>随着第一台计算机的诞生，硬件与软件就成了构成计算机系统的两个重要组成部分，它们相伴而生、相互促进，它们分工迥异、各司其职。为了使用和驱动不断演化的硬件系统，通过计算机语言来编写系统和应用程序的方式逐渐确立了主流的地位。伴随着高级编程语言的出现，第一代编译器也在20世纪50年代产生了，它实现了高级语言到机器代码的等价转换，完成了人类认知到机器“认知”的转换。而几乎与此同时，将机器码还原成为高级语言的逆向思考也引发了研究人员的求知欲望。</p>

<p>在第一代编译器出现十年之后的20世纪60年代，以小规模集成电路为特征的第三代计算机开始出现。由于其与第二代晶体管计算机的差异较大，使得运行在第二代计算机上的软件几乎面临着即将被全部淘汰的危险。然而基于当时的软件开发技术和开发成本，淘汰软件意味着巨大的损失。为了挽救这些价值不菲的软件，同时也为了加速开发第三代机器的软件，与软件移植技术相关的研究逐渐兴起，例如：程序转换器、交叉汇编器、翻译器、反编译器等。其中反编译器成了最初的研究热点。</p>

<p><strong>1) D-Neliac——反编译器的开山祖师</strong></p>

<p>一些美国公司和研究机构开始着手进行软件移植工具的研究，并且由美国海军电子实验室的J.K.Donally和H.Englander在1960年实现了第一代反编译器D-Neliacdecompiler。由此我们的反编译器鼻祖正式“粉墨登场”了，比它的兄弟“编译器”整整小了10岁。Donnelly-Neliac（D-Neliac）可以将机器代码反编译成Neliac（类似于Algol的一种编程语言，是NEL在1955年开发的一个Algol-Algorithmiclanguage类型语言）程序代码。</p>

<p><strong>2) Sassaman的Fortran反编译器——不是一个人的江湖</strong></p>

<p>无独有偶，1966年Sassaman在TRW公司开发了一个反编译器，该反编译器以IBM 7000序列的符号化汇编程序做为输入并产生Fortran程序，是第一个使用汇编程序而非纯二进制代码作为输入的反编译器。它是有据可查的第二个正式的反编译器，但是由于它以包含大量有用信息的符号化汇编程序作为输入，而省却了反汇编的过程，也因此降低了反编译的难度。这是第一个使用汇编程序而非纯二进制代码作为输入的反编译器。汇编程序包含名字、宏、数据和指令形式的有用信息，在二进制程序或者可运行程序中是没有这些信息的，因此避免了在反编译器的语法分析阶段区分数据和指令的问题。</p>

<p>又因为该反编译器的输出是1960年代的标准编程语言Fortran程序（第二代、第三代计算机上都在使用Fortran），所以使得它看起来更具有实用意义。该反编译器面向的是涉及代数运算的工程应用程序，使用者需要掌握一定的相关知识，并能够为子程序的识别自定义规则。在熟练的程序员干预下，该反编译器的正确率可以达到90%，因此它是属于少数人的“阳春白雪”。</p>

<p><strong>3)Lockheed Neliac——开山祖师的传人</strong></p>

<p>1967年，洛克希德导弹与空间公司在海军电子实验室开发的Neliac编译器上做了一些增强，我们称它为Lockheed Neliac。</p>

<p>反编译器LockheedNeliac与D-Neliac类似，它们都可将机器代码程序转换成Neliac程序代码，特别是它们可以将非Neliac语言生成的机器代码转换为Neliac程序代码。这一时期的反编译器采用模式匹配的方法进行反编译，把许多复杂的问题留给程序员手工解决。</p>

<p><strong>4)小结——De-compiler的拓荒者们</strong></p>

<p>整个60年代，反编译方面的研究主要集中在研制专门用途的反编译器上，并希望其可以作为软件移植的工具来使用。但是受限于当时计算机发展水平，以及体系结构的影响，这一时期的反编译器主要采用模式匹配的方法进行反编译，需要较多的人工干预；并且反编译的结果通常不经过优化处理，所以输出的结果代码效率较低、可读性较差。</p>

<p>从前边的叙述中可以看出，尽管从编译器被发明以来，人们就对编译的逆过程倍感兴趣，但真正迈出这关键的一步却是由于进行“软件移植”的诉求。那个年代的计算机程序停留在大型商业公司和高等院校的实验室里，只有很少的人能接触和掌握高级语言的编程，程序的复杂程度也较为有限，也没有大量出现病毒，因此利用反编译进行程序分析并没有那么重要。</p>

<h3>2.发展——20世纪70年代</h3>

<p>反编译技术建立初期，并没有很快成为通用的商业软件流行起来。大学校园的理论研究，成为推动这项技术发展的主要动力。下面我们按照时间的脉络，走进历史进程中的“象牙塔”，回顾一下反编译技术的发展过程。反编译理论方面的研究成为这个时期的热门，随着美国多位博士以反编译作为博士研究课题，一些对逆向编译和程序移植有一定影响的理论和技术被相继提出。在这个研究领域，豁然呈现出百花齐放的景象。</p>

<p><strong>1)花开一朵——博士们的研究</strong></p>

<p>1973年，DoctorHollander首次针对反编译方式生成的代码，使用控制流与数据流分析相结合的技术手段来进行优化。此外，他还基于元语言描述定义了一个反编译过程的五级模型，并且实现了从IBM System360汇编子集到类ALGOL语言的反编译。该反编译器虽然引入了一些新的技术，即综合利用数据流和控制流分析技术来改善反编译器的输出代码，并使用形式化方法来分析代码，但其核心依然是构筑在模式匹配技术基础之上。</p>

<p>几乎在同时，DoctorHousel的博士论文对反编译进行了较系统的论述，文中描述了一种可行的反编译方法，并通过实验验证了部分理论。Housel的反编译方法借用编译器、图、和优化理论的概念，并据此设计了一种包括部分汇编、分析器、代码生成等三个主要步骤的反编译器。然而受限于当时实验平台和目标程序，Housel仅仅测试了6个程序。实验中，有88%的指令可以通过反编译器自动生成，剩余的指令则需要程序员进行手工干预。这个反编译器证明，通过使用已知的编译器和图的方法，可以实现生成良好高级代码的反编译器。中间表示法的使用使得分析完全不依赖机器。这个方法学的主要缺陷在于源语言的选择，MIX汇编语言，在这些程序中不仅带有大量可用信息，而且它是一个简单化的、非现实的汇编语言。</p>

<p>1974年，DoctorFriedman在他的博士学位论文中描述了一个反编译器，用于在相同体系结构等级内的小型计算机操作系统的迁移。该编译器包含四个主要部分：前期处理器、反编译器、代码生成器、和编译器，它是Housel反编译器的一个改写版。Friedman在反编译操作系统代码的方向上迈出了第一步，而且它例证了在反编译机器依赖的代码时反编译器面对的困难。不足的是，该迁移系统对输入程序有所要求，即需要对输入程序做大量格式化工作；同时，该系统最后产生的程序代码具有较大的空间膨胀率，而代码膨胀率高又带来了执行时间和效率的低下。</p>

<p>1978年，DoctorHopwood所做的工作实现了从汇编语言程序到MOL620语言程序的翻译功能。他引入了控制流图的概念，即指定一条指令作为控制流图的一个节点。与现在广为采用的以基本块为节点的方式相比，Hopwood的方案对内存的要求会更高一些。Hopwood的博士学位论文描述了有关其设计的一个包含七个步骤的反编译器的内容，他的研究的主要缺点是控制流向图的粒度和在最后的目标程序中寄存器的使用。其中控制流向图的粒度的使用，导致该反编译器处理大规模程序的时候开销太大；而在其所生成的目标高级语言代码中使用了寄存器，导致反编译结果并非纯正的高级代码。</p>

<p><strong>2)花开二朵——反编译技术在工程上的应用</strong></p>

<p>20世纪70年代的十年是反编译技术发展的一个黄金时期，当时的反编译器并未局限在对高级编程语言的恢复上，而是引入了“翻译”的特征。在这个时期，除了一些以理论研究为主的反编译器模型被提出以外，还有一些具有代表性的实用系统被开发出来。</p>

<p>1974年，由Barbe开发的Piler系统是第一个实现的X型通用反编译器架构，它的设计目标是实现从多种机器级代码到与其各自对应的高级语言程序的反编译。但是这种多源到多目标的反编译实现起来具有极高的难度，直接导致Piler系统最终实现时，仅能支持从通用公司的Honeywell 600机器代码到Fortran和COBOL两种高级语言程序的反编译。可见，当时的反编译器如果能够实现对“翻译”输出的高级语言再次编译，并且编译后程序的运行结果与反编译前一致的话，就几乎相当于一个二进制翻译器了。</p>

<p><strong>3)花开三朵——反编译技术在军事上的应用</strong></p>

<p>反编译技术同样被军方慧眼识珠，在上世纪70年代多项军事应用中可以看到它的身影。</p>

<p>1974年，Ultrasystems公司的一个反编译工程中也用到了反编译器。这个反编译器作为三叉戟 (Trident)潜艇射击控制软件系统的一个文档编写工具。它以Trident汇编程序作为输入，产生这个公司开发的Trident高级语言程序。该编译器分成四个主要阶段：规格化、分析、表达式凝聚和代码生成。该系统的输入为经过“规格化预处理”的汇编程序，其目的是为了解决部分指令和数据的区分问题；与此同时，预处理过程还会生成一种中间表示，并对数据进行分析；然后，在表达式凝聚的过程期间，算术表达式和逻辑表达式将被还原并建立；最后，再通过和THLL（Ultra systems公司的名为Trident的高级语言）匹配控制结构，而生成输出的高级语言程序。</p>

<p>1978年，D.A.Workman主导了一项有军方背景的反编译应用研究，目的是为美国军方实时训练装置系统设计适用的高级语言。该应用在F4型教练机的相关设计中发挥了作用。F4教练机的操作系统是用汇编语言编写的，因此这个反编译器的输入语言是汇编语言。由于这项应用的目标是用于设计，因此没有确定输出语言，没有实现代码生成，仅仅实现了反编译器的两个阶段：阶段一，把汇编程序映射为一个中间语言并收集关于源程序的统计信息；阶段二，产生基本块的控制流向图，依据它们的可能类型来划分指令，并且分析控制流以确定高级控制结构。这项成果的贡献在于，提出了一种在当时看起来十分独特的反编译技术应用。即这个反编译器，并未以输出高级语言代码为最终目的，而是通过把指令分类来进行数据分析。从这一案例，可以看出反编译技术的先进性在当时得到了美国军方的认可，并且在实际应用中催生出了代码分析的功能，值得后续研究的借鉴。</p>

<p><strong>4)小结</strong></p>

<p>有了1960年代的技术积累，反编译技术在高等院校得到了理论和实践的双重推进。在理论研究的支撑下，越来越多的实用系统中都使用了反编译技术。以至于被大家公认的高科技技术集散地的美国军方，也将反编译技术投入到军事训练和实战中。因此，在1970年代反编译技术拥有自己完美的发展期，并获得了长足的进步。</p>

<h3>3.瓶颈期——20世纪80年代</h3>

<p>之所以将1980年代称为反编译发展的瓶颈期，主要是这项技术所能实现的功能的合法性问题。毕竟随着计算机的普及和发展，软件知识产权逐步被人们所重视。反编译技术可以逆向获得程序源代码的特性，与软件知识产权的保护存在着一定的矛盾。如何界定科学研究和非法获利，一时没有定论，但是这个十年中，相关研究也没有完全停滞，仍然有一些具有代表性的工作。</p>

<p><strong>1) Zebra</strong></p>

<p>1981年，美国军方的另一个反编译实例：美国海军水下系统中心开发的Zebra样机试图实现汇编程序的可移植性。Zebra的主要功能是把ULTRA/32汇编语言的一个名叫AN/UYK-7的子集作为输入语言，进而产生PDP-11/70的汇编程序输出。尽管Zebra并不是传统意义的反编译器，更像是单纯的程序移植和变换，但是该系统的实现方式与反编译并没有什么不同，即Zebra的实现主要由三大步骤构成。第一阶段，词汇和流分析：对原程序进行解析，并在基本块内做控制流分析；第二阶段，程序被翻译为中间形式；第三阶段，做中间表示的化简。</p>

<p>Zebra利用已知的技术来开发一个汇编程序的反编译器，整个研发过程并没有引入新的概念。但是Zebra提出一个观点值得我们回味，也就是说：从Zebra的研发过程中看出，反编译应该作为一个工具帮助解决某个问题，而不是完全解决该问题的工具。这个结论，源于科研人员对反编译的了解而提出的假设，即假如反编译器不可能达到100%正确。虽然这是一个上世纪80年代初就提出的论断，但我们仍然可以从中一窥反编译发展至今的主要作用——程序分析（相关的讨论，我们放到相应的章节来具体讨论）。</p>

<p><strong>2)Forth Decompiler</strong></p>

<p>1982到1984年，Forth Decompiler系统具有一定的代表性。它是一种可以通过递归扫描Forth语言编译字典条目，而把单词反编译成原语和地址的一个工具。但是Forth Decompiler并不是一个纯正的反编译器，它更像是一个逆语法分析工具，该工具递归地扫描一个字典表并且返回与给定单词有关的原语或地址。</p>

<p><strong>3)STS（SoftwareTransport System）</strong></p>

<p>1985年，C.W. Yoo介绍了软件传输系统STS （SoftwareTransport System），实现汇编代码从一机器到另一机器的自动转换。STS的转换思路是：将机器m1的汇编代码反编译成高级语言程序，然后将获得的程序在机器m2上编译成新的汇编代码。一个实验型的STS系统是针对Z-80处理器而研发的C语言交叉编译器，但是由于STS系统缺少数据类型信息导致此项目搁浅。</p>

<p><strong>4)Decomp</strong></p>

<p>1988年，Reuter编写了一套反编译器，并命名为Decomp，它是一种专用于Vax BSD 4.2机器的反编译器。Decomp需要带有符号信息的目标文件作为反编译的输入，而通过反编译生成类C源码程序，部分输出的C源码经过手工编辑后可以被再次编译。Decomp做了一件今天看起来十分有趣的事情，也就是它为了一款游戏而生，它在没有可用源代码的情况下把帝国游戏(Empire)移植到VMS环境。这件事情与笔者目前从事的二进制翻译相关研究非常类似，即实现了应用程序级别的移植，并以游戏这种生动的形式加以展示。</p>

<p>Decomp反编译器在当时的条件下，花费了大概5人月的工作量，并且可以从因特网上免费获取它。昆士兰大学的Cristina Cifuentes在她的博士论文中，成功地重现了Decomp的反编译过程。从实验中可以看出，Decomp反编译生成的程序有正确的控制结构、正确的变量数据类型、库例程和子过程的名字，甚至用户程序入口点也得到了还原。当然上述功能的取得，都需要满足一定的先决条件，但仅从功能上来看，Decomp是一个又实用价值的反编译器。</p>

<p><strong>5)小结</strong></p>

<p>经过20年的技术积累，1980年代本来应该成为反编译技术的爆发期，但是由于它天生的逆向属性，导致其与软件知识产权的保护产生了矛盾。在法律监管的空白时间里，并没有产生一些让我们记忆犹新的优秀系统和应用。整个1980年代的研究延续了不温不火的态势，但是对反编译完备性的讨论和实用化的驱使，仍然使得这个方向的研究延续下来。这个10年的研究比1970年代更注重实用性，并从专用这个角度加以体现。</p>

<h3>4.反编译的春天——20世纪90年代</h3>

<p>1990年代，反编译技术作为一个主体终于有了可以依据的法律——许多国家针对软件逆向工程进行立法，以规范该领域的研究工作。从一篇美国研究者Pamela Samuelson的文章“Reverse-engineering SomeoneElse's Software: Is It Legal？”中，可以重现当时美国对“反编译”这一类技术的法律定义：根据美国联邦法律，对拥有版权的软件进行逆向工程操作，例如反汇编、反编译，若其目的不是通过剖析原软件，来研制新产品与之竟争，所进行的逆向操作是合法的。仔细品味这句话可知，只要是非盈利性的软件分析和源代码获取是被允许的。在上述背景下，反编译技术迎来了发展的春天，一批国家层面的综合性研究项目代表了反编译在当时的地位，比如：由11个欧洲工业和学术组织合作研究的REDO计划，主要是以调查研究软件的维护、有效性和软件系统文档化为目标。他们在软件逆向工程研究主题下对反编译进行了大量研究，从逻辑语义上给出反编译的一些实现方法和本质描述，并将其结果应用于英国核工业部。既然春天来了，除了上述枝叶返青的参天大树，哪能没有百花齐放呢？我们再把1990年代的反编译发展脉络梳理一下。</p>

<p>此外，在这个十年中，反编译这项技术与另外一项称作“二进制翻译”的技术结合的越来越紧密。反编译技术作为二进制翻译的一种重要实现方式，我们将在后文详细介绍二者的联系和区别，同时也会花一定篇幅，着重揭开一下能够体现反编译技术实用性的“二进制翻译”的神秘面纱。</p>

<p><strong>1) Exe2c</strong></p>

<p>1990年，由AustinCode Works公司推出的实验项目Exe2c可以将Intel80286/DOS可执行程序反汇编，并转换为内部格式代码，最终转换成C程序。从Exe2c的输出代码看出，它并没有实现数据流分析，而仅仅实现了部分控制流分析。C语言使用的一些控制结构被恢复，如：if-then和循环。它生成的C语言程序的大小是汇编程序的3倍。这个反编译器的积极意义在于，它是在过去的若干年中第一个尝试反编译可运行文件的反编译器。其成果表明，为了产生更好的C代码需要引入一个较为完善的数据流分析和启发式功能。而且，建立一个忽略所有由编译器引进的外来代码和发现库子程序的机制会很有帮助。这一点可以大大降低反编译的工作量，同时提升反编译输出的可用性。</p>

<p><strong>2) PLM-80 Decompiler</strong></p>

<p>1991年研发的PLM-80Decompiler反编译器也是一款具有国家支持和军事应用背景的软件，它是澳大利亚国防部的信息技术司研究的一个反编译的国防应用，也是在“反编译的春天”里值得一提的一项研究。PLM-80Decompiler研发的主要目的是针对废弃代码的维护、具有科技情报产品的分析、以及针对信息系统的安全和保密风险的评估，其中除了第一点以外，其它的目的都与反编译在当今时代的需求所契合，可见该项目在当时是具有前瞻意义的一项研究。</p>

<p>虽然研发目标具有重要意义，但最终由于技术实现的难度，PLM-80Decompiler只实现了一个样机。该样机是用Prolog语言编写的，针对特定机器PLM-80编译器编译的Intel 8085汇编程序，可以产生一种称作“Small-C语言”的目标程序（Small-C代表所生成的代码是标准C语言的子集）。从公开可以查阅的文献中，可以了解到PLM-80Decompiler可以从输入的汇编程序中识别出部分if..then和while()等简单结构，可以还原一些int和char等简单的数据类型，以及一些全局和局部变量。除此之外，PLM-80Decompiler还设计了一个图形化用户界面用于显示汇编程序和伪C程序，并且用户还可以通过图形界面编辑变量的名字、增加注解，以及支持手工确定主程序的入口点等功能。</p>

<p>总的来说，PLM-80Decompiler所做的分析局限于控制结构和简单数据类型的识别，并没有引入针对寄存器使用的分析。同时，该反编译器也不支持分析编译器生成的优化代码。但值得称道的是，PLM-80Decompiler对图形界面的引入，是对用户体验的一次提升，也是对反编译这种需要人工反馈参与工作的一种新的支持手段。</p>

<p><strong>3) 8086 C Decompiling System</strong></p>

<p>1991年推出的8086C Decompiling System是一个将Intel 8086/DOS可执行程序翻译成C程序的反编译器。它实现了库函数的识别以减少生成代码的量，同时它基于规则识别出了数组和结构体的指针等数据类型。不出意外的是，这个反编译器同样对输入文件有特殊的要求——输入文件必须是由Microsoft C V5.0版本小存储器模型编译所生成的。这一点再一次印证了:一个反编译器的可用性受限于它对源编译器的依赖。多数反编译器只能针对特定的编译器类型（或者编译器版本）完成正确的反编译动作。</p>

<p>8086 C Decompiling System描述了五个阶段：库函数的识别、符号执行、数据类型识别、程序转换和C语言代码生成。</p>

<p>该系统在库函数识别阶段所做的工作具有一定代表性，很多反编译器和后来的二进制翻译器都采用类似的方法。有必要单独说明一下：8086 C DecompilingSystem主要实现了对Microsoft C库函数的识别，用来区分哪些是系统调用的库函数，哪些是用户自己编写的函数。这么做的目的是为了在反编译时只处理用户函数，生成相应的C代码，而所有库函数则不必被反编译。识别库函数是通过模板匹配的形式完成，即预先构造一个所有C语言的库函数表，包含一些特殊信息，这部分工作是反编译器作者手工实施的。</p>

<p>除了库函数识别阶段以外，该反编译器其余阶段的实施中规中矩。它的符号执行是将机器指令完全用特有符号来表示，形成一套中间指令；而对数据类型的识别则是通过两套规则配合来实现的，即首先通过一组规则对于不同数据类型进行信息收集，然后再根据所收集的信息和另外一组分析规则共同确定数据类型；程序转换则把存储计算转变成各种地址表达式，例如数组寻址；最后，C语言代码生成器通过识别控制结构，继而转换成相应的程序结构，并且生成C语言代码。</p>

<p>8086 C Decompiling System是由我国合肥工业微机所科研人员开发的一套较早的反编译系统，代表了当时我国的反编译研究的方向和水平。</p>

<p><strong>4) Alpha AXP Migration Tools</strong></p>

<p>数字装备公司(Digital Equipment Corporation)在设计Alpha AXP体系结构的时候，需要能够在“新”的Alpha AXP计算机上运行“现有”的VAX和MIPS代码。正是由于这个动议，使得Alpha AXP MigrationTools作为一套可以完成上述功能的二进制翻译工具被开发出来。Alpha AXPMigration Tools可以实现旧体系结构的指令序列转换成新体系结构的指令序列，即实现不同体系结构间二进制级代码的无缝移植。这个移植过程中被开发者定义成两个部分，分别是：二进制翻译过程和运行时环境。为了保证二进制翻译过程的全自动执行，同时能够实现执行期间创建或修改代码的功能，该移植工具在二进制翻译部分使用了反编译技术。</p>

<p>Alpha AXP Migration Tools中反编译技术的应用，主要体现在机器指令的潜在含义理解和分析上。例如：原体系结构上的条件码分析，以便后续翻译过程中可以转化为Alpha体系结构上的相应操作；通过代码分析，确定函数的返回值或者发现代码中的错误；MIPS中标准库例程的发现和定位，以减少代码翻译的工作量，因为库例程绝大多数情况下是可以在新体系架构中找到类似库函数实现其功能的；发现代码中的“成语”（可以理解为在特定体系结构上，完成特定功能的一组指令序列），并使用目标体系结构中功能等价的指令组合来实现该“成语”的功能。通过上述一系列的分析工作，以及其他翻译工作，最终以AXP操作码的形式组成翻译后的二进制编码，并由运行时环境执行翻译的代码。</p>

<p>这个工程举例说明在一个现代翻译系统中反编译技术的使用。证明对于众多类别的二进制程序来说它是成功的。一些无法翻译的程序是在技术上不可翻译的程序，比如使用特权操作码的程序或者以超级用户特权运行的程序。</p>

<p><strong>5) 其它反编译器产品和研究</strong></p>

<p>在这一阶段还有众多公司纷纷推出自己的反编译器产品，具体情况如表所示。</p>

<p>表1 20世纪90年代部分反编译器产品</p>

<table>
<thead>
<tr>
  <th>产品名称</th>
  <th>年份</th>
  <th>用途</th>
  <th>厂商</th>
</tr>
</thead>
<tbody>
<tr>
  <td>Valkyrie</td>
  <td>1993</td>
  <td>用于 Clipper Summer '87 的可视化反编译器</td>
  <td>CodeWorks</td>
</tr>
<tr>
  <td>OutFox</td>
  <td>1993</td>
  <td>用于加密的FoxBASE+程序的反编译器</td>
  <td>不详</td>
</tr>
<tr>
  <td>ReFox</td>
  <td>1993</td>
  <td>用于反编译加密的FoxPro文件</td>
  <td>Xitech</td>
</tr>
<tr>
  <td>DOC</td>
  <td>1993</td>
  <td>用于 AS/400 和 System/38 的COBOL反编译器</td>
  <td>Harman Resources</td>
</tr>
<tr>
  <td>Uniclip</td>
  <td>1993</td>
  <td>用于 Clipper Summer '87 EXE 文件的反编译器</td>
  <td>Stro Ware</td>
</tr>
<tr>
  <td>Clipback</td>
  <td>1993</td>
  <td>用于Summer '87 可执行文件的反编译器</td>
  <td>Intelligent Information Systems</td>
</tr>
<tr>
  <td>Brillig</td>
  <td>1993</td>
  <td>用于 Clipper 5.X .exe文件和.obj文件的反编译器</td>
  <td>APTware</td>
</tr>
</tbody>
</table>

<p>同时也有一批大学的实验室，发表自己的试验系统，其中在这一领域Cifuentes博士的研究成果，成为以后反编译研究的主要参考方向。Cifuentes在自己的博士论文中指出，可以通过数据流分析识别参数和返回值，通过控制流分析将代码恢复成具有结构的C程序。研究型反编译器dcc展现了她的工作，但它只能处理很小的Intel 80286/DOS可执行程序。</p>

<p>在dcc的基础上，反编译器REC（Reverse Engineering Compiler）基于Cifuentes的工作在几个方面进行了扩展，但是它生成的类C程序比较难读，因为包含了寄存器符号。它可以处理多个处理器（如：Intel 386、Motorola 68K）上运行的多种格式的可执行文件（如：ELF和Windows PE等）。像数组等复杂的数据类型保留为访问内存的表达式。</p>

<h3>5.持续的研究——进入21世纪</h3>

<p>时间荏苒，当历史的脚步进入新世纪，反编译的相关研究也随之更进一步，本节我们将用简单的笔触介绍2000年后的相关研究和商用产品。</p>

<p>2001年，Guilfanov介绍了IDA Pro反汇编器使用的类型传播系统，并着重讲解了库函数的识别工作。IDA Pro利用库函数的签名信息来恢复库函数调用语句使用的参数的数据类型，然后使用类型传播技术处理赋值语句来进行数据类型恢复。上述事实说明，没有一种数据类型恢复不是根据库函数类型信息进行的。</p>

<p>2002年，Morisada发布了处理32位Windows可执行程序的反编译器Anatomizer。对某些Windows可执行程序它表现的很出色，可以恢复参数和返回值，条件语句和switch语句也得到了很好的处理。当使用Anatomizer处理Cygwin程序时，库函数printf无法被恢复。另外，Anatomizer无法处理浮点指令和间接调用，数组仍然被保留为访问内存的表达式。当寄存器在某些过程体中未被定值而先使用时，它无法将其识别成参数。反编译器Anatomizer经常会异常终止。</p>

<p>2002年，Tröger和Cifuentes给出一个分析间接调用指令的方法。如果由虚函数产生的间接调用被成功识别，那么关于此间接调用的诸多信息都会获得。然而，此方法受限于一个基本块的范围，导致无法处理所有的情况。</p>

<p>2004年，RaimarFalke基于Mycroft的理论并进行扩展开发了反编译器Yadec，用于恢复数组数据类型。但需要一个相当于用户抉择的文件来处理冲突。</p>

<p>2004年，由AndreyShulga编写的反编译器Andromeda一直没有公开发行，但从网站可以获得一个GUI程序对应反编译生成程序。生成程序给人的印象非常深刻，但不能仅凭一个反编译生成程序来断定反编译器的优劣，可能它恢复出的数据类型是经过手工编辑的。</p>

<p>2007年，IlfakGuilfanov发布一个集成反汇编器IDA Pro的反编译器Hex-Rays，用来处理32位Windows可执行程序。反编译器Hex-Rays可以在窗口中展示反编译生成的类C代码，通过点击函数名跳到函数体视窗。所有函数的参数和返回值都得到了恢复，但作者声明反编译生成的程序仅用于阅读，不能对其进行编译。</p>

<p>遗憾的是，2008年后国外与反编译紧密的相关的重要研究很难再被检索到。笔者分析，其主要原因是反编译本身的复杂性，不完备性，以及在逆向分析实践中不如反汇编实用的现实所造成的。此外，虚拟化技术的日渐成熟，也分化了相当一部分使用反编译形式进行二进制翻译的研究资源。</p>

<h3>6.身边的反编译——我国对反编译的研究</h3>

<p>国内从事反编译方面研究的团队较少，能够在公开报道中查证的有：从1984年开始，合肥工业大学微机所开展了一系列与反编译相关的研究工作：在国家自然科学基金的资助下，以Dual-68000为硬件平台，研制T 68000 C反编译系统；用手工的方法反编译了UNIX操作系统部分组件；七•五期间，他们还进行了8086 C语言反编译系统的研究；随后，他们还发布了商业化的反编译系统DECLER V1.0和V1.1。1991年发表的文献中提及，武汉大学从1986年起就开始研制VAX机上的C语言反编译系统。同年发表的另外一篇文献中提及，北京控制工程研究所在PC机上开发TC语言反编译系统。1992年，上海交通大学的科研人员也发表了关于VAX机器上C语言反编译系统研究与实现的论文。1994年哈尔滨工业大学的研发团队开发了一款基于Turbo C的小模式反编译系统。2001年，解放军信息大学开始研发ITA二进制翻译系统（历时五年)，该系统可以实现将IA64/Lunix架构下由C语言编制的可执行程序反编译到SW/Lunix下执行。2006年，北京大学计算机科学研究所研发了汇编级别的分析工具BESTAR。该工具实现了Linux平台上的轻量级汇编代码结构化表示功能，它能够实现利用控制流和数据流分析技术识别通用控制结构。该工具还可以分析程序执行流，重构表达式和函数，发现数据依赖关系，将汇编代码转换成一个结构化、易理解的中间语言程序。</p>

<p>当然前文还提到了8086 CDecompiling System也是国内非常重要的研究和工作，尤其8086 C Decompiling System还在Cifuentes的论文中被提及。</p>

<p>最后 ，致谢 小楠楠，借鉴了他大段文字。经过博士论文撰写，发现你文笔水平大增啊！</p>      </p>
    
			</body>
		</html>
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          